P1560 [USACO5.2]蜗牛的旅行

这道题是一道典型的搜索题,我们用dfs(x,y,step,s)dfs(x,y,step,s)表示蜗牛在(x,y)(x,y)这个点,走了stepstep步,当前的方向(起点的s=0s=0,特殊处理一下)。

当蜗牛确定一个方向后,我们就不断让它前进,同时记录它走过的格子,直到它遇到障碍,出界或者到达已走过的点停止。

如果蜗牛遇到障碍,我们就枚举每个方向,因为前方有障碍,后方已经走过,所以蜗牛只会向左或向右转,不需要特殊处理。

代码中gotogoto的作用是找到后面的单词,使之跳过一些语句,感觉作用比breakbreak,continuecontinue强,可以减少一些判断。

最后是代码:

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 120;
char x;
int n,m,y,Ans;
char Map[ MAXN + 5 ][ MAXN + 5 ];
bool vis[ MAXN + 5 ][ MAXN + 5 ];

int tx[ 5 ] = { 0 , 1 , -1 , 0 , 0 };
int ty[ 5 ] = { 0 , 0 , 0 , 1 , -1 };
void dfs( int x , int y , int step , int s ) {
	Ans = max( Ans , step );
	if( s ) {
		int fx = x + tx[ s ] , fy = y + ty[ s ];
		if( fx == 0 || fy == 0 || fx == n + 1 || fy == n + 1 || Map[ fx ][ fy ] == '#' )
			goto there;
		if( vis[ fx ][ fy ] )
			return;
		vis[ fx ][ fy ] = 1;
		dfs( fx , fy , step + 1 , s );
		vis[ fx ][ fy ] = 0;
		return;
	}
	there:;
	for( int i = 1 ; i <= 4 ; i ++ ) {
		int fx = x + tx[ i ] , fy = y + ty[ i ];
		if( fx == 0 || fy == 0 || fx == n + 1 || fy == n + 1 || Map[ fx ][ fy ] == '#' || vis[ fx ][ fy ] )
			continue;
		vis[ fx ][ fy ] = 1;
		dfs( fx , fy , step + 1 , i );
		vis[ fx ][ fy ] = 0;
	}
}

int main( ) {
	scanf("%d %d",&n,&m);
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= n ; j ++ )
			Map[ i ][ j ] = '.';
	for( int i = 1 ; i <= m ; i ++ ) {
		cin >> x;
		scanf("%d",&y);
		Map[ y ][ x - 'A' + 1 ] = '#';
	}
	/*for( int i = 1 ; i <= n ; i ++ ) {
		for( int j = 1 ; j <= n ; j ++ )
			printf("%c",Map[ i ][ j ]);
		printf("\n");
	}*/
	vis[ 1 ][ 1 ] = 1;
	dfs( 1 , 1 , 1 , 0 );
	printf("%d",Ans);
	return 0;
}